package sort;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{9, 4, 6, 8, 3, 10, 4, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int low, int high) {
        int p, i, j, temp;
        if (low >= high) {
            return;
        }
        //p就是基准数,这里就是每个数组的第一个
        p = arr[low];
        i = low;
        j = high;
        while (i < j) {
            //右边当发现小于p的值时停止循环
            while (arr[j] >= p && i < j) {
                j--;
            }
            //这里一定是右边开始，上下这两个循环不能调换（下面有解析，可以先想想）
            //左边当发现大于p的值时停止循环
            while (arr[i] <= p && i < j) {
                i++;
            }
            temp = arr[j];

            arr[j] = arr[i];
            arr[i] = temp;
        }
        //这里的arr[i]一定是停小于p的，经过i、j交换后i处的值一定是小于p的(j先走)
        arr[low] = arr[i];
        arr[i] = p;
        //对左边快排
        quickSort(arr, low, j - 1);
        //对右边快排
        quickSort(arr, j + 1, high);

    }

}
